package OptimalAlgorithm.BitOperation;
//给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
//eg:
//输入：n = 2
//输出：[0,1,1]
//解释：
//0 --> 0
//1 --> 1
//2 --> 10

public class CountBits {
    public int[] countBits(int n) {
        int[] ret = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            int count = 0;
            int j = i;
            while (j != 0){
                j = j & (j - 1);//干掉一个数二进制表示中最右侧的1
                count++;
            }
            ret[i] = count;
        }
        return ret;
    }
}
